#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
单调递增二进制字符串最小翻转次数 - 算法实现
"""

class Solution:
    def minFlipsMonoIncr(self, s: str) -> int:
        """
        单调递增二进制字符串最小翻转次数算法
        使用动态规划，维护两个状态：
        - dp0: 当前字符为0时的最小翻转次数
        - dp1: 当前字符为1时的最小翻转次数
        """
        dp0 = dp1 = 0
        
        for c in s:
            # 保存当前状态
            dp0New, dp1New = dp0, min(dp0, dp1)
            
            # 根据当前字符更新状态
            if c == '1':
                # 当前字符是1，如果要保持为0需要翻转
                dp0New += 1
            else:
                # 当前字符是0，如果要保持为1需要翻转
                dp1New += 1
            
            # 更新状态
            dp0, dp1 = dp0New, dp1New
        
        return min(dp0, dp1)

def simple_min_flips_mono_incr(s: str) -> int:
    """简化版算法，用于验证"""
    if not s:
        return 0
    
    # 统计每个位置前面有多少个1，后面有多少个0
    n = len(s)
    ones_before = [0] * (n + 1)
    zeros_after = [0] * (n + 1)
    
    # 计算每个位置前面1的个数
    for i in range(n):
        ones_before[i + 1] = ones_before[i] + (1 if s[i] == '1' else 0)
    
    # 计算每个位置后面0的个数
    for i in range(n - 1, -1, -1):
        zeros_after[i] = zeros_after[i + 1] + (1 if s[i] == '0' else 0)
    
    # 找到最小翻转次数
    min_flips = float('inf')
    for i in range(n + 1):
        # 在位置i分割：前面全为0，后面全为1
        flips = ones_before[i] + zeros_after[i]
        min_flips = min(min_flips, flips)
    
    return min_flips

def test_algorithm():
    """测试算法"""
    solution = Solution()
    
    # 测试用例
    test_cases = [
        ("00110", 1),
        ("010110", 2),
        ("00011000", 2),
        ("0", 0),
        ("1", 0),
        ("00", 0),
        ("11", 0),
        ("01", 0),
        ("10", 1)
    ]
    
    print("算法测试结果:")
    print("=" * 30)
    
    for s, expected in test_cases:
        result = solution.minFlipsMonoIncr(s)
        status = "✓" if result == expected else "✗"
        print(f"{status} s='{s}'")
        print(f"    期望: {expected}, 实际: {result}")
        print()

if __name__ == "__main__":
    test_algorithm() 